package heap_sort

//HeapSort 堆排序
//最好 O(nlogn), 平均：O(nlogn), 最差 O(nlogn)
//不稳定的排序算法
func HeapSort(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	i := 0
	for i < ln {
		buildSmallestHeap(nums[i:])
		i++
	}
	return nums
}

func buildSmallestHeap(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	i := ln -1
	for i > 0 {
		p := (i+1) / 2 - 1
		if nums[i] < nums[p] {
			nums[i], nums[p] = nums[p], nums[i]
		}
		i--
	}
	return nums
}